package sit.engreal.leetcode.problems700;

import java.util.ArrayDeque;

/**
 * <a href="https://leetcode.cn/problems/max-area-of-island/">695. 岛屿的最大面积</a>
 */
public class LeetCode695 {

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        final int m = grid.length;
        final int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] <= 0) {
                    continue;
                }
                final int area = areaOfIsland(grid, m, n, i, j);
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        return maxArea;
    }

    private int areaOfIsland(int[][] grid, int m, int n, int pi, int pj) {
        final ArrayDeque<int[]> deque = new ArrayDeque<>();
        deque.offerLast(new int[]{pi, pj});
        int area = 1;
        grid[pi][pj] = -grid[pi][pj];

        while (!deque.isEmpty()) {
            final int[] p = deque.pollFirst();
            final int i = p[0];
            final int j = p[1];

            if (i - 1 >= 0 && grid[i - 1][j] > 0) {
                area++;
                grid[i - 1][j] = -grid[i - 1][j];
                deque.offerLast(new int[]{i - 1, j});
            }
            if (i + 1 < m && grid[i + 1][j] > 0) {
                area++;
                grid[i + 1][j] = -grid[i + 1][j];
                deque.offerLast(new int[]{i + 1, j});
            }
            if (j - 1 >= 0 && grid[i][j - 1] > 0) {
                area++;
                grid[i][j - 1] = -grid[i][j - 1];
                deque.offerLast(new int[]{i, j - 1});
            }
            if (j + 1 < n && grid[i][j + 1] > 0) {
                area++;
                grid[i][j + 1] = -grid[i][j + 1];
                deque.offerLast(new int[]{i, j + 1});
            }
        }
        return area;
    }

    public static void main(String[] args) {
        final LeetCode695 demo = new LeetCode695();
        {
            final int[][] grid = new int[][]{
                    {1, 1, 0, 0, 0},
                    {1, 1, 0, 0, 0},
                    {0, 0, 0, 1, 1},
                    {0, 0, 0, 1, 1}
            };
            final int area = demo.maxAreaOfIsland(grid);
            System.out.println(area);
        }
        {
            final int[][] grid = new int[][]{
                    {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                    {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                    {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                    {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                    {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                    {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                    {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
            };
            final int area = demo.maxAreaOfIsland(grid);
            System.out.println(area);
        }

    }

}
